package rmmk.zadanie1;

public class Recursively implements ISort {

	public Integer[] sort(Integer[] array) {
		if (array.length > 2) {
			return this.joinArrays(
					this.sort(this.getSmallerOrEqualElements(array)),
					array[0],
					this.sort(this.getBiggerElements(array)));
		} else
			return array;
	}

	private Integer[] getSmallerOrEqualElements(Integer[] array) {
		if (array.length > 0) {
			Integer[] smaller = new Integer[countSmallerOrEqual(array)];

			int index = 0;
			for (int i = 1; i < array.length; ++i)
				if (array[i] <= array[0])
					smaller[index++] = array[i];

			return smaller;
		} else
			return new Integer[0];
	}

	private Integer[] getBiggerElements(Integer[] array) {
		Integer[] bigger = new Integer[countBigger(array)];

		int index = 0;
		for (int i = 1; i < array.length; ++i)
			if (array[i] > array[0])
				bigger[index++] = array[i];

		return bigger;
	}

	private int countSmallerOrEqual(Integer[] array) {
		int count = 0;

		if (array.length > 0) {
			Integer first = array[0];

			for (int i = 1; i < array.length; ++i)
				if (array[i] <= first)
					++count;
		}
		return count;
	}

	private int countBigger(Integer[] array) {
		return array.length - countSmallerOrEqual(array) - 1;
	}

	private Integer[] joinArrays(Integer[] a, Integer m, Integer[] b) {
		Integer[] c = new Integer[a.length + b.length + 1];

		int index = 0;
		for (Integer d : a)
			c[index++] = d;
		
		c[index++] = m;
		
		for (Integer d : b)
			c[index++] = d;

		return c;
	}
}
